package leetcode;

import util.LinkList;
import util.ListNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0148.java
 * @Author : WangRuoyu
 * @Date 2023/11/19 21:19
 */

public class Q0148 {
    // 合并两个有序链表 O(1)空间复杂度
    public ListNode mergeList(ListNode p, ListNode q) {
        if (p.val > q.val) {
            ListNode tmp = p;
            p = q;
            q = tmp;
        }

        ListNode head = new ListNode(-1, p);
        ListNode pre = head;

        while (p != null && q != null) {
            if (p.val <= q.val) {
                pre = p;
                p = p.next;
                continue;
            }
            ListNode tmp = q.next;
            q.next = p;
            pre.next = q;
            pre = q;
            q = tmp;
        }

        if (q != null) {
            pre.next = q;
        }

        return head.next;
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = head;
        ListNode q = head.next;

        while (q.next != null && q.next.next != null) {
            p = p.next;
            q = q.next.next;
        }

        ListNode tmp = p.next;
        p.next = null;
        p = sortList(head);
        q = sortList(tmp);

        return mergeList(p, q);
    }

    public static void main(String[] args) {
        Q0148 sl = new Q0148();
//        int[] a = {1, 3, 5};
//        int[] b = {2, 4, 6};
//        LinkList.printList(sl.mergeList(LinkList.createList(a), LinkList.createList(b)));

        int[] node = {-1, 5, 3, 4, 0};
        ListNode head = LinkList.createList(node);
        LinkList.printList(sl.sortList(head));
    }
}